﻿#define _CRT_SECURE_NO_WARNINGS 1
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//思路
//前序创建树，中序分割左右子树，子树区间确认是否继续递归创建子树
//前序创建根，中序分割区间
//用当前前序的数去创建根，
//在中序中找到创建根的数，分割成左右区间。
//左区间递归创建子树，右区间递归创建子树。如果中序区间不存在结束递归

#include<bits/stdc++.h>
using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend)//previ前序确定位置 inbegin inend中序区间
    {
        //4.中序区间不存结束
        if (inbegin > inend) return nullptr;


        //1.前序创建根
        TreeNode* root = new TreeNode(preorder[previ]);
        previ++;
        //2.分割中序
        int ini = inbegin;
        while (ini <= inend)
        {
            if (inorder[ini] == root->val)
            {
                break;
            }
            else ini++;
        }
        //[inbegin   ini-1] ini [ini+1   inend]
        //3.递归创建左右并链接
        root->left = _buildTree(preorder, inorder, previ, inbegin, ini - 1);
        root->right = _buildTree(preorder, inorder, previ, ini + 1, inend);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        TreeNode* root = _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
        return root;

    }
};